package TextBinaryTree;

import java.util.ArrayList;
import java.util.List;

public class TextBinaryTree {
    public static class TreeNode {
        public char val;//数据域
        public TreeNode left; //左孩子的引用
        public TreeNode right;//右孩子的引用
        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode root;//二叉树的根节点

    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }
    // 前序遍历
    void preOrder(TreeNode root){
        if (root == null) {
            return;
        }
        System.out.println(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    // 中序遍历
    void inOrder(TreeNode root){
        if (root == null) {
            return;
        }
        preOrder(root.left);
        System.out.println(root.val + " ");
        preOrder(root.right);
    }
    // 后序遍历
    void postOrder(TreeNode root){
        if (root == null) {
            return;
        }
        preOrder(root.left);
        preOrder(root.right);
        System.out.println(root.val + " ");
    }
    List<Integer> list = new ArrayList<>();
    // 二叉树前序非递归遍历实现  它是有返回值的，要合理的利用返回值
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
           return list;
        }
        //首先打印的过程就是把数据添加到list的过程
        list.add((int) root.val);
        List<Integer> leftTree = preorderTraversal(root.left);
        list.addAll(leftTree);
        List<Integer> rightTree = preorderTraversal(root.right);
        list.addAll(rightTree);
        return list;
    }
    //获取树中节点的个数
    //时间复杂度：O（N）      空间复杂度： O（logN）因为当递归调用的时候在栈上开辟栈帧，
    //                                当左边遍历完成之后，左边的栈帧就会被回收，再去开辟右边的栈帧
    public int size(TreeNode root) {//子问题思路
        if (root == null) {
            return 0;
        }
        int left = size(root.left);
        int right = size(root.right);
        return left +right + 1;//在归的过程中就把这些节点数加起来了。
    }

    public int nodeSize = 0;
    public int size2(TreeNode root) {//遍历思路
        if (root == null) {
            return 0;
        }else {
            nodeSize++;
        }
        size(root.left);
        size(root.right);
        return nodeSize;
    }
    //获取叶子节点的个数：左右子树都是空的时候就是一个节点
    public int getLeafNodeCount(TreeNode root) {//子问题思路
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int left = getLeafNodeCount(root.left);
        int right = getLeafNodeCount(root.right);
        return left + right;
    }
    public int count;
    public int getLeafNodeCount2(TreeNode root) {//遍历思路
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            count++;//一边遍历一边++
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return count;
    }
    //获取第k层的叶子节点
    //思路：算第k层，就需要算左子树的第k-1层和右子树的第k-1层，然后相加
    //例：算root的第三层节点数，就需要算左子树的第二层节点数和右子树的第二层的节点数
    //要算左子树的第二层节点数，就要算左子树的左子树的第一层节点数，依次类推
    int getKLeveNOdeCount(TreeNode root,int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
       int left =  getKLeveNOdeCount(root.left,k-1);
        int right = getKLeveNOdeCount(root.right,k-1);
        return left + right;
    }
    //获取二叉树的高度
    //思路；就是左子树的高度和右子树的高度取最大值然后加上一个根节点的高度
    int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHieght = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        int maxHeight = leftHieght < rightHeight ? rightHeight :leftHieght;
        return maxHeight + 1;
    }
    //判断是否为平衡二叉树
    //判断左子树和右子树是否平衡
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        int leftHieght = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if (Math.abs(leftHieght-rightHeight) <= 1) {
            return true;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }
    public int getHeight2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHieght = getHeight(root.left);
        if (leftHieght < 0) return -1;
        int rightHeight = getHeight(root.right);
        if (rightHeight < 0) return -1;
        //在求高度的过程中，如果一棵子树的左子树和右子树差的绝对值超过了1，就说明这颗树已经不平衡了
        //所以就不需要再去求右子树的高度了（站在A节点的角度），时间复杂度就是O（N）
        if (Math.abs(leftHieght-rightHeight) < 2) {
            return Math.max(leftHieght,rightHeight);
        }else {
            return -1;
        }
    }
    //在o（n）的时间复杂度内求二叉树是否为平衡二叉树
    public boolean isBalanced2(TreeNode root) {
        return getHeight2(root) >= 0;
    }
    public boolean isSameTree(TreeNode p,TreeNode q) {
        //思路：先看头节点是否相同，相同再去判断左子树是否相同，
        // （判断左子树先看左子树的节点是否为空，不为空再判断值是否相同）
        //  再去判断右子树.....
        //一个为空一个不为空
        if (p == null && q != null || p != null && q == null) return false;
        if (p == null && q == null) return true;
        if (p.val != q.val) return false;
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
    //另一颗数树的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null || subRoot == null) {
            return false;
        }
        if (isSameTree(root,subRoot)) {
            return true;
        }
        if (isSameTree(root.left,subRoot) || isSameTree(root.right,subRoot)) {
            return true;
        }
        return false;
    }
    //对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return false;
        //去判断它的左边和右边是否是对称的
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode leftRoot,TreeNode rightRoot) {
        //一个为空，一个不为空
        if (leftRoot == null && rightRoot != null ||
                leftRoot != null && rightRoot == null) {
            return false;
        }
        //两个都是空的
        if (leftRoot == null && rightRoot == null) {
            return true;
        }
        //两个都不是空的，就判断值是否相等
        if (leftRoot.val != rightRoot.val) return false;
        return isSymmetricChild(leftRoot.left,rightRoot.right) &&
                isSymmetricChild(leftRoot.right,rightRoot.left);
    }
    //判断两颗树是否相同
    public boolean isSameTree2(TreeNode p, TreeNode q) {
        if (p == null && q != null || p != null && q == null) {
            return false;
        }
        if (p == null && q == null) {
            return true;
        }
        //都不为空
        if (p.val != q.val) return false;
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
    //反转二叉树
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root);
        return root;
    }
}
